package src.leetcode.dp.medium_0337;

import src.tree.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;

public class rob {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(3,2,3,null,3,null,1));
        TreeNode root = TreeNode.createTree(list);
        System.out.println(solution.rob(root));
    }
}

class Solution {
    public int rob(TreeNode root) {
        int []res = dfs(root);
        return Math.max(res[0],res[1]);
    }

    private int[] dfs(TreeNode root){
        int []res = new int[2];
        if(root == null) return res;

        int []left = dfs(root.left);
        int []right = dfs(root.right);

        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = left[0] + right[0] + root.val;
        return res;
    }
}
